/*
 * Copyright 2012 LinkedIn Corp.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */

var maxTextSize = 32;
var reductionSize = 26;
var degreeRatio = 1/8;
var maxHeight = 200;
var cornerGap = 10;

var idSort = function(a, b) {
	if ( a.id < b.id ) {
		return -1;
	}
	else if ( a.id > b.id ) {
		return 1;
	}
	else {
		return 0;
	}
}

function prepareLayout(nodes, hmargin, layers, nodeMap) {
	var maxLayer = 0;
	var nodeQueue = new Array();
	// Find start layers first
	for (var i=0; i < nodes.length; ++i) {
		var node = nodes[i];
		if (node.inNodes) {
			// We sort here. Why? To keep the node drawing consistent
			node.in.sort(idSort);
		}
		else {
			// We sort here. Why? To keep it up and running.
			nodeQueue.push(node);
		}
	}
	// Sort here. To keep the node drawing consistent
	nodes.sort(idSort);
	
	// calculate level
	// breath first search the sucker
	var index = 0;
	while(index < nodeQueue.length) {
		var node = nodeQueue[index];
		if (node.inNodes) {
			var level = 0;
			for (var key in node.inNodes) {
				level = Math.max(level, node.inNodes[key].level);
			}
			node.level = level + 1;
		}
		else {
			node.level = 0;
		}
		
		if (node.outNodes) {
			for (var key in node.outNodes) {
				nodeQueue.push(node.outNodes[key]);
			}
		}
		index++;
	}
	
	// Assign to layers
	for (var i = 0; i < nodes.length; ++i) {
		var width = nodes[i].width ? nodes[i].width : nodes[i].label.length * 11.5 + 4;
		var height = nodes[i].height ? nodes[i].height : 1;
		var node = { id: nodes[i].id, node: nodes[i], level: nodes[i].level, in:[], out:[], width: width + hmargin, x:0, height:height };
		nodeMap[nodes[i].id] = node;
		maxLayer = Math.max(node.level, maxLayer);
		if(!layers[node.level]) {
			layers[node.level] = [];
		}
		
		layers[node.level].push(node);
	}
	
	layers.maxLayer = maxLayer;
}

function respaceGraph(nodes, edges) {
	
}

function layoutGraph(nodes, edges, hmargin) {
	var startLayer = [];

	var nodeMap = {};
	var layers = {};
	
	if (!hmargin) {
		hmargin = 8;
	}
	
	prepareLayout(nodes, hmargin, layers, nodeMap);
	var maxLayer = layers.maxLayer;
	
	// Create dummy nodes
	var edgeDummies = {};
	for (var i=0; i < edges.length; ++i ) {
		var edge = edges[i];
		var src = edges[i].from;
		var dest = edges[i].to;
		
		var edgeId = src + ">>" + dest;
		
		var srcNode = nodeMap[src];
		var destNode = nodeMap[dest];
		
		var lastNode = srcNode;

		var guides = [];
		
		for (var j = srcNode.level + 1; j < destNode.level; ++j) {
			var dummyNode = {level: j, in: [], x: lastNode.x, out: [], realSrc: srcNode, realDest: destNode, width: 10, height: 10};
			layers[j].push(dummyNode);
			dummyNode.in.push(lastNode);
			lastNode.out.push(dummyNode);
			lastNode = dummyNode;
			
			guides.push(dummyNode);
		}
		
		destNode.in.push(lastNode);
		lastNode.out.push(destNode);
		
		if (edgeDummies.length != 0) {
			edgeDummies[edgeId] = guides;
		}
	}

	spreadLayerSmart(layers[maxLayer]);
	sort(layers[maxLayer]);
	for (var i=maxLayer - 1; i >=0; --i) {
		uncrossWithOut(layers[i]);
		sort(layers[i]);
		
		spreadLayerSmart(layers[i]);
	}

	// The top level can get out of alignment, so we do this kick back
	// manouver before we seriously get started sorting.
	if (maxLayer > 1) {
		uncrossWithIn(layers[1]);
		sort(layers[1]);
		spreadLayerSmart(layers[1]);

		uncrossWithOut(layers[0]);
		sort(layers[0]);
		spreadLayerSmart(layers[0]);
	}

	// Uncross down
	for (var i=1; i <= maxLayer; ++i) {
		uncrossWithIn(layers[i]);
		sort(layers[i]);
		spreadLayerSmart(layers[i]);
	}

	// Space it vertically
	spaceVertically(layers, maxLayer);
	
	// Assign points to nodes
	for (var i = 0; i < nodes.length; ++i) {
		var node = nodes[i];
		var layerNode = nodeMap[node.id];
		node.x = layerNode.x;
		node.y = layerNode.y;
	}

	// Dummy node for more points.
	for (var i = 0; i < edges.length; ++i) {
		var edge = edges[i];
		var src = edges[i].from;
		var dest = edges[i].to;
		
		var edgeId = src + ">>" + dest;
		if (edgeDummies[edgeId] && edgeDummies[edgeId].length > 0) {
			var prevX = nodeMap[src].x;
			var destX = nodeMap[dest].x; 
			
			var guides = [];
			var dummies = edgeDummies[edgeId];
			for (var j=0; j< dummies.length; ++j) {
				var point = {x: dummies[j].x, y: dummies[j].y};
				guides.push(point);
				
				var nextX = j == dummies.length - 1 ? destX: dummies[j + 1].x; 
				if (point.x != prevX && point.x != nextX) {
					// Add gap
					if ((point.x > prevX) == (point.x > nextX)) {
						guides.push({x: point.x, y:point.y + cornerGap});
					}
				}
				prevX = point.x;
			}
						
			edge.guides = guides;
		}
		else {
			edge.guides = null;
		}
	}
}

function spreadLayerSmart(layer) {
	var ranges = [];
	ranges.push({
		start: 0, 
		end: 0, 
		width: layer[0].width, 
		x: layer[0].x, 
		index: 0
	});
	var largestRangeIndex = -1;
	
	var totalX = layer[0].x;
	var totalWidth = layer[0].width;
	var count = 1;
	
	for (var i = 1; i < layer.length; ++i ) {
		var prevRange = ranges[ranges.length - 1];
		var delta = layer[i].x - prevRange.x;
				
		if (delta == 0) {
			prevRange.end = i;
			prevRange.width += layer[i].width;
			totalWidth += layer[i].width;
		}
		else {
			totalWidth += Math.max(layer[i].width, delta);
			ranges.push({
				start: i, 
				end: i, 
				width: layer[i].width, 
				x: layer[i].x, 
				index: ranges.length
			});
		}
		
		totalX += layer[i].x;
		count++;
	}

	// Space the ranges, but place the left and right most last
	var startIndex = 0;
	var endIndex = 0;
	if (ranges.length == 1) {
		startIndex = -1;
		endIndex = 1;
	}
	else if ((ranges.length % 2) == 1) {
		var index = Math.ceil(ranges.length/2);
		startIndex = index - 1;
		endIndex = index + 1;
	}
	else {
		var e = ranges.length/2;
		var s = e - 1;
		
		var crossPointS = ranges[s].x + ranges[s].width/2;
		var crossPointE = ranges[e].x - ranges[e].width/2;
		
		if (crossPointS > crossPointE) {
			var midPoint = (ranges[s].x + ranges[e].x)/2;
			ranges[s].x = midPoint - ranges[s].width/2;
			ranges[e].x = midPoint + ranges[e].width/2;
		}
		
		startIndex = s - 1;
		endIndex = e + 1;
	}
	
	for (var i = startIndex; i >= 0; --i) {
		var range = ranges[i];
		var crossPointS = range.x + range.width/2;
		var crossPointE = ranges[i + 1].x - ranges[i + 1].width/2;
		if (crossPointE < crossPointS) {
			range.x -= crossPointS - crossPointE;
		}
	}
	
	for (var i = endIndex; i < ranges.length; ++i) {
		var range = ranges[i];
		var crossPointE = range.x - range.width/2;
		var crossPointS = ranges[i - 1].x + ranges[i - 1].width/2;
		if (crossPointE < crossPointS) {
			range.x += crossPointS - crossPointE;
		}
	}
	
	for (var i = 0; i < ranges.length; ++i) {
		var range = ranges[i];
		if (range.start == range.end) {
			layer[range.start].x = range.x;
		}
		else {
			var start = range.x - range.width/2;
			for (var j=range.start;j <=range.end; ++j) {
				layer[j].x = start + layer[j].width/2;
				start += layer[j].width;
			}
		}
	}
}

function spaceVertically(layers, maxLayer) {
	var startY = 0;
	var startLayer = layers[0];
	var startMaxHeight = 1;
	for (var i=0; i < startLayer.length; ++i) {
		startLayer[i].y = startY;
		startMaxHeight = Math.max(startMaxHeight, startLayer[i].height);
	}
	
	var minHeight = 40;
	for (var a=1; a <= maxLayer; ++a) {
		var maxDelta = 0;
		var layer = layers[a];
		
		var layerMaxHeight = 1;
		for (var i=0; i < layer.length; ++i) {
			layerMaxHeight = Math.max(layerMaxHeight, layer[i].height);

			for (var j=0; j < layer[i].in.length; ++j) {
				var upper = layer[i].in[j];
				var delta = Math.abs(upper.x - layer[i].x);
				maxDelta = Math.max(maxDelta, delta);
			}
		}
		
		console.log("Max " + maxDelta);
		var calcHeight = maxDelta*degreeRatio;
		
		var newMinHeight = minHeight + startMaxHeight/2 + layerMaxHeight / 2;
		startMaxHeight = layerMaxHeight;

		startY += Math.max(calcHeight, newMinHeight);
		for (var i=0; i < layer.length; ++i) {
			layer[i].y=startY;
		}
	}
}

function uncrossWithIn(layer) {
	for (var i = 0; i < layer.length; ++i) {
		var pos = findAverage(layer[i].in);
		layer[i].x = pos;
	}
}

function findAverage(nodes) {
	var sum = 0;
	for (var i = 0; i < nodes.length; ++i) {
		sum += nodes[i].x;
	}
	return sum/nodes.length;
}

function uncrossWithOut(layer) {
	for (var i = 0; i < layer.length; ++i) {
		var pos = findAverage(layer[i].out);
		layer[i].x = pos;
	}
}

function sort(layer) {
	layer.sort(function(a, b) {
		return a.x - b.x;
	});
}
